#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int res=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){res=(res<<1)+(res<<3)+(c^48);c=getchar();}
	return res*f;
}
void write(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
int t;
int n,m;
struct node
{
	int u,v,w;
	bool operator<(const node &a)const{return w<a.w;}
}e[3005*3005];
int cnt;
int dis[3005][3005];
int f[3005];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
signed main()
{
	freopen("up.in","r",stdin);
	freopen("up.out","w",stdout);
	t=read();
	while(t--)
	{
		n=read(),m=read();
		if(!m) 
		{
			write(n-1),puts("");
			continue;
		}
		cnt=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++) dis[i][j]=-1;
		for(int i=1;i<=m;i++)
		{
			int u=read(),v=read(),w=read();
			dis[u][v]=dis[v][u]=w;
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(dis[i][j]==-1) dis[i][j]=abs(i-j);
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
				e[++cnt]=(node){i,j,dis[i][j]};
		sort(e+1,e+cnt+1);
		for(int i=1;i<=n;i++) f[i]=i;
		int ans=0;
		for(int i=1;i<=cnt;i++)
		{
			int fx=find(e[i].u),fy=find(e[i].v);
			if(fx==fy) continue;
			ans+=e[i].w;
			f[fx]=fy;
		}
		write(ans),puts("");
	}
	return 0;
}
